/*
 * optimal.c
 *
 *  Created on: 17 sept. 2013
 *      Author: the
 */

#include"optimal.h"

//variant 1: on alloue toutes les radios.
//variant 2: on s'arrete des que l'on a la topologie initial.
int computeOptimal(int variant)
{
	int i;

	//On assigne la valeur maximal possible a minConflict pour rechercher ensuite le minimum.
	minConflict=MAXCONFLICT;

	//Copie de la topology qui conservera l'optimal. L'assignation radio sera copie colle apres dans l'original (a la fin).
	//Les calculs des tables de routages se faisant apres, il n'y a pas besoin de l'alloue pour celui ci.
	//Pour le calcul du voisinage et 2 voisinage il n'y pas besoin de mettre jour car il n'est pas corrompu dans l'original.
	if((copyNodes=(struct node *) malloc(nbOfNodes*sizeof(struct node)))==NULL) error("Error: main() -> malloc nodes");

	//On desalloue les radio 0
	for(i=0;i<nbOfNodes;i++) nodes[i].frequency[0]=-1;

	//Algorithme recursif qui explore toutes les allocations possibles
	if(variant==1) allocateOptimal(0,0,0);
	else if(variant==2) allocateOptimal2(0,0,0);
	else{
		fprintf(stderr,"Valeur de variante incorrecte (%d): doit etre 1 ou 2\n",variant);
		exit(3);
	}

	//On remet l'alllocation optimal dans "nodes"
	saveTopology(copyNodes,nodes);

	free(copyNodes);

	return(1);
}

//Algorithme recursif qui explore toutes les allocations possibles
//et sauvegarde l'optimal dans copyNodes
void allocateOptimal(int id, int radio, int minFreq)
{

	int freq, conflict, i, cpt;

	//On alloue une frequence differente pour chaque radio.
	//Les frequences alloues sont dans l'ordre croissant (par ex. (1,4,7) pour les radios 0, 1 et 2)
	//On passe donc un argument (minFreq) indiquant la premiere frequence allouable.


	//Explication de "maxFreq-(nbOfRadios-radio))+1" dans la boucle for.
	//On essaye de gagner en nombres de possibilites a explorer:
	//pour reduire le nombre de combinaison, on considere que la couleur (freq) de la radio 0 du noeud 0
	//est 0 (cela peut etre vu non pas comme la freq 0 mais comme la frequence de la radio 0 noeud 0),
	//la deuxieme radio est forcement 1, etc.
	//
	cpt=id*nbOfRadios+radio;
	for(freq=minFreq;freq<MIN(cpt,maxFreq-(nbOfRadios-radio))+1;freq++)
	{
		//On alloue la freq a cette radio
		allocationFreq(id,radio,freq);

		//DEBUG

		if((id<=2+nbOfRadios)&&(radio<=1)){
			for(i=0;i<=id;i++)
				fprintf(stderr,"n%d r%d f%d r%d f%d-",i,0,nodes[i].frequency[0],1,nodes[i].frequency[1]);
				//if(!(i%2)) fprintf(stderr,"n%d r%d f%d-",i,0,nodes[i].frequency[0]);
			fprintf(stderr,"\n");
		}


		//Toutes les radios pour ce noeud ne sont pas encore alloues
		if(radio<=nbOfRadios-2) allocateOptimal(id,radio+1,freq+1);

		//Toutes les radios sont affectees, on test d'abord si les contraintes (liens avec tous les voisins) sont verifies
		//si elles ne le sont pas on desalloue et on arrete (on revient un cran en arriere).
		if((radio==nbOfRadios-1)&&(!verifyConstraints(id))){
			//fprintf(stderr,"Ne verifie pas les contraintes\n");
			freeRadio2(id, radio);
			return;
		}

		//Sinon, on passe au noeud suivant (en commencant par sa premiere radio d'indice 0 et freq=0).
		if((radio==nbOfRadios-1)&&(id<=nbOfNodes-2)) allocateOptimal(id+1,0,0);

		//Dernier cas de figure: tout est alloue ; on traite...
		if((radio==nbOfRadios-1)&&(id==nbOfNodes-1)){
			//Si le graphe obtenu est "topology preserving" on regarde son graphe des conflits
			if(preserveTopology()){
				conflict=conflictGraph(0);
				//if(conflict>MAXCONFLICT){
				if(conflict>9999999){
					fprintf(stderr,"Erreur allocateOptimal(): la valeur de MAX_CONFLICT est trop petite\n");
					exit(3);
				}
				//Si c'est la meilleur allocation: on la sauvegarde
				if(conflict<minConflict){
					saveTopology(nodes,copyNodes);
					minConflict=conflict;
				}
			}//fin du if(preserveTopology())
		}//
	}//fin du for sur freq

	//On desalloue cette radio (redescente de l'algo).
	freeRadio2(id, radio);

}//end of function allocateOptimal()

//Algorithme recursif qui explore toutes les allocations possibles
//et sauvegarde l'optimal dans copyNodes
//La difference avec la premiere version est que l'on s'arrete des que l'on a une topologie qui
//preserve la topology. Toutes les radios ne sont donc pas forcement assignees comme pour l'autre.
void allocateOptimal2(int id, int radio, int minFreq)
{

	int freq, conflict, cpt;

	//On alloue une frequence differente pour chaque radio.
	//Les frequences alloues sont dans l'ordre croissant (par ex. (1,4,7) pour les radios 0, 1 et 2)
	//On passe donc un argument (minFreq) indiquant la premiere frequence allouable.

	//Explication de "maxFreq-(nbOfRadios-radio))+1" dans la boucle for.
	//On essaye de gagner en nombres de possibilites a explorer:
	//pour reduire le nombre de combinaison, on considere que la couleur (freq) de la radio 0 du noeud 0
	//est 0 (cela peut etre vu non pas comme la freq 0 mais comme la frequence de la radio 0 noeud 0),
	//le deuxieme noeud a soit la meme couleur (0) soit une differente (freq 1), etc.
	//
	cpt=id+radio*nbOfNodes;
	for(freq=minFreq;freq<MIN(cpt,maxFreq-(nbOfRadios-radio))+1;freq++)
	{
		//On alloue la freq a cette radio
		allocationFreq(id,radio,freq);
		//DEBUG
		//if( ((id<=9)&&(radio==0)) || ((id<=2)&&(radio==1)) ){
		/*
		if((id<=9)&&(radio==0)){
			for(i=0;i<=9;i++)
				fprintf(stderr,"n%d f%d-",i,nodes[i].frequency[0]);
			fprintf(stderr,"---");
			//for(i=0;i<=2;i++)
			//	fprintf(stderr,"n%d f%d-",i,nodes[i].frequency[1]);
			fprintf(stderr,"\n");
		}
		*/

		//On test d'abord si les contraintes (liens avec tous les voisins) sont verifies
		//si elles ne le sont pas on desalloue et on arrete (on revient un cran en arriere).
		if((radio==nbOfRadios-1)&&(!verifyConstraints(id))){
			freeRadio2(id, radio);
			return;
		}

		//Si le graphe obtenu est "topology preserving" on regarde son graphe des conflits
		//et on arrete.
		if(preserveTopology()){
			conflict=conflictGraph(0);
			//if(conflict>MAXCONFLICT){
			if(conflict>9999999){
				fprintf(stderr,"Erreur allocateOptimal(): la valeur de MAX_CONFLICT est trop petite\n");
				exit(3);
			}
			//Si c'est la meilleur allocation: on la sauvegarde
			if(conflict<minConflict){
				saveTopology(nodes,copyNodes);
				minConflict=conflict;
			}
		}else{
			//Si ce n'est pas topology preserving (pas encore), on continue d'alloue (tant qu'il y a des radios de libres).
			//Tous les noeuds n'ont pas encore la radio 0 allouee
			if((id<=nbOfNodes-2)&&(radio==0)) allocateOptimal2(id+1,0,0);
			//On passe au noeud suivant pour cette radio
			else if(id<=nbOfNodes-2) allocateOptimal2(id+1,radio,nodes[id+1].frequency[radio-1]+1);
			//On a alloue a tous les noeuds la radio "radio". On refait une passe sur tous les noeuds pour la radio suivante.
			else if(radio<=nbOfRadios-2) allocateOptimal2(0,radio+1,nodes[0].frequency[radio]+1);
			//Dernier cas de figure: tout est alloue ; on arrete (on ne fait rien)...

		}//fin du if(verifyConstraints())
	}//fin du for sur freq

	//On desalloue cette radio (redescente de l'algo).
	freeRadio2(id, radio);

}//end of function allocateOptimal2()


void allocationFreq(int id, int radio, int freq)
{
	nodes[id].frequency[radio]=freq;
}

void freeRadio2(int id, int radio)
{
	//On assigne -1 a la radio pour indiquer qu'elle est libre.
	nodes[id].frequency[radio]=-1;
}


//Retourne 1 si l'assignation actuelle est "topology preserving"
//Retourne 0 autrement (il y a deux voisins du graphe initiale qui n'ont pas de frequences en commun).
int preserveTopology()
{
	int i, j;

	//Pour tous les noeuds, on regarde si il y a un lien avec tous ses voisins
	for(i=0;i<nbOfNodes;i++)
		for(j=0;j<nodes[i].nbN1;j++)
			if(linkExist2(i,nodes[i].N1[j].id)==0){

				//DEBUG
				/*
				fprintf(stderr,"link (%d,%d) is missing\n",i,nodes[i].N1[j]);
				fprintf(stderr,"Frequency node %d=",i);
				for(k=0;k<nbOfRadios;k++) fprintf(stderr,"%d ",nodes[i].frequency[k]);
				fprintf(stderr,"\n");
				fprintf(stderr,"Frequency node %d=",nodes[i].N1[j].id);
				for(k=0;k<nbOfRadios;k++) fprintf(stderr,"%d ",nodes[nodes[i].N1[j].id].frequency[k]);
				fprintf(stderr,"\n");
				*/


				return(0);
			}

	return(1);
}

//Verify that the node id, has a link with all its neighbors.
//We checck only if node id has all its radios assigned and only
//for neighbors with all their radios assigned.
int verifyConstraints(int id)
{
	int i, index, allocated;

	//If id has no neighbor: it verifies the constraints
	if(nodes[id].nbN1==0) return(1);

	//If the number of radios assigned to node id is less than nbOfRadios, it verifies the constraints (in fact we do not know yet).
	allocated=nbOfAllocatedRadio(id);
	if(allocated<nbOfRadios) return(1);
	if(allocated>nbOfRadios){
		fprintf(stderr,"Erreur verifyConstraints(): le nombre de radios alloue est > le nombre de radios\n");
		exit(4);
	}

	//allocated==nbOfRadio
	for(i=0;i<nodes[id].nbN1;i++){
		index=nodes[id].N1[i].id;
		//If this neighbor has all its radio assigned, we verify that id has a common freq with it.
		if(nbOfAllocatedRadio(index)==nbOfRadios)
			if(linkExist2(id,index)==0) return(0);
	}

	//If it has a common freq with all its neighbors we return 1
	return(1);
}

//Return the number of radios assigned (!=-1) to node id.
int nbOfAllocatedRadio(int id)
{
	int i, cpt=0;

	for(i=0;i<nbOfRadios;i++) if(nodes[id].frequency[i]!=-1) cpt++;

	return(cpt);
}

void saveTopology(struct node* source, struct node* destination)
{
	int i, j;

	for(i=0;i<nbOfNodes;i++)
		for(j=0;j<nbOfRadios;j++)
			destination[i].frequency[j]= source[i].frequency[j];
}
